\documentclass[10pt]{amsart}

\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{tikz}
\usepackage[all]{xy}

\renewcommand{\familydefault}{\sfdefault}
\setlength\parindent{0cm}

\newtheorem*{defn}{Definition}
\DeclareMathOperator{\ord}{ord}
\DeclareMathOperator{\Aut}{Aut}
\DeclareMathOperator{\Prob}{Prob}
\DeclareMathOperator{\Tree}{Tree}

\title{Theorem 4.2}
\date{}

\begin{document}
\maketitle

This theorem is a generalization of theorem 2.11 which uses less machinery, mainly because we heavily use covering maps.

\subsection*{Statement}
Let $H$ be a graph whose maximal degree is no more than $d \geq 3$, then for any $d$-regular graph $G$ on $n$ vertices which contains the graph $H$ as a subgraph we have the following lower bound on the second largest eigenvalue of the graph $G$:
\[
\lambda_2(G ) \geq \lambda_1(\Tree_d(H))- o_n(1)
\]
Where $\Tree_d(G)$ is the $d$-regular tree completion of the graph $H$.

\subsection*{Detailed proof}
Denote by $T$ the $d$-regular tree completion of the graph $F$. Fix  an $\varepsilon > 0$, we'll show that $\lambda_2(G) \geq \lambda_1(T)  - \varepsilon$ for any $d$-regular graph $G$ on $n$ vertices as long as $n$ is large enough.

(NOT SO GOOD IN TERMS OF DEFINITIONS HERE) By definition of the largest eigenvalue of an infinite graph, there must exist a function $f$ on the $T$, the $d$-regular tree completion of the graph $H$, with a finite support such that
\[
\lambda_1(T) - \epsilon \leq \frac{||Bf||}{||f||}
\]
Where $B$ is the adjacency operator of the graph $T$.

(USING TECHNICAL STUFF THAT I DON'T UNDERSTAND YET,  some Dirichlet eigenfunctions among other things) WE CAN ASSUME THE FOLLOWING: We can assume that the function $f$ is non-negative and that it satisfies
\[
Bf \geq (\lambda_1(T)-\epsilon)f
\]
with equality everywhere except on the boundary of the graph $H$ (IS THAT USEFUL?).

\subsection*{Lemma}
Let $\pi: H \rightarrow G$ be a covering map and let $f$ be a function on the vertices of the graph $H$, then the following holds:
\[
(A_G(\pi_*f))(v) = \sum_{w \in \pi^{-1}(v)}(A_Hf)(w)
\]
\begin{proof}
Just develop the sum, it comes out very naturally.
\end{proof}

\subsection*{(BACK TO THE MAIN PROOF)}

We claim that the following holds:
\[
A_G(\pi_*f) \geq (\lambda_1(T)-\epsilon)(\pi_*f)
\]
Indeed, we have that
\begin{align*}
(A_G(\pi_*f))(v) &= \sum_{w \in \pi^{-1}(v)}Bf(w)\\
&\geq \sum_{w \in \pi^{-1}(v)}(\lambda_1(T)-\epsilon)f(w)\\
&= (\lambda_1(T) - \epsilon)\sum_{w \in \pi^{-1}(v)}f(w)\\
&= \left(\lambda_1(T) - \epsilon\right)\pi_*f(v)
\end{align*}

This allows to estimate the Rayleigh quotient of the function $\pi_*f$ as follow:
\[
R_G(\pi_*f) = \frac{\langle A_G(\pi_*f),\pi_*f \rangle }{ \langle \pi_*f,\pi_*f \rangle} \geq \lambda_1(T)-\epsilon
\]
by non-negativity of the function $f$ and thus of the function $\pi_*f$ as well.\\

Using LEMMA I DON'T KNOW WHERE YET SAYING HOW TO FIND LOWER BOUNDS ON THE SECOND LARGEST EIGENVALUE USING ORTHOGONAL FUNCTIONS, we'll show that we can find an function $g$ which is orthogonal to both functions $\pi_*f$ and $A_G(\pi_*f)$ and whose Rayleigh quotient is larger than the Rayleigh quotient of $\pi_*f$.

Denote by $N$ the support of the function $\pi_*f$ and denote by $N_1$ the set of all vertices at distance at most 1 from the set $N$ (in other words, $N_1$ is the closed ball centred at the set $N$ of radius 1 in the usual distance metric of the graph). We'll define the function $g=1_{V \backslash N_1}$ to be the characteristic function of the complement of the set $N_1$. By construction, the function $g$ is orthogonal to both functions $\pi_*f$ and $A_G(\pi_*f)$ since it takes zero values everywhere those two functions potentially take non-zero values.

Let's estimate the Rayleigh quotient of the function $g$ now. The denominator can be computed precisely:
\[
\langle g,g \rangle = |V \backslash N_1| = n - |V_1|
\]
The numerator can be estimated as follow:
\[
\langle A_Gg,g \rangle = \sum_{v \notin N_1} (A_Gg)(v) \geq d(n-d|N_1|)
\]
where the lower bound is obtained by only counting the vertices $v$ at distance at least 2 from the set $N_1$ for which we'll have $(A_Gg )(v)=d$ since all neighbours of such a vertex $v$ cannot belong to the set $N_1$. There are at least $n-d |N_1|$ of such vertices which explains the lower bound. We thus obtain the following estimate on the Rayleigh quotient of the function $g$
\[
R_G(g) = \frac{\langle A_Gg,g \rangle}{\langle g,g \rangle} \geq \frac{d(n-d|N_1|)}{n-|N_1|}=d-\frac{d(d-1)|N_1|}{n-|N_1|}
\]
Note that $|N_1|$ the size of the vertices at distance at most 1 from the support of the function $\pi_*f$ is of size ... TO DO.

\end{document}